#!/usr/bin/env python
# -*-coding:utf-8-*-
# @Time : 2021/10/14 17:39
# @Author : Li Yan
import copy
import math

select_digit = {1, 2, 3, 4, 5, 6, 7, 8, 9}

s_data = [
    [None, 3, None, None, 7, None, None, None, None],
    [6, None, None, 1, 9, 5, None, None, None],
    [None, 9, 8, None, None, None, None, 6, None],
    [8, None, None, None, 6, None, None, None, 3],
    [4, None, None, 8, None, 3, None, None, 1],
    [7, None, None, None, 2, None, None, None, 6],
    [None, 6, None, None, None, None, 2, 8, None],
    [None, None, None, 4, 1, None, None, None, 5],
    [None, None, None, None, 8, None, None, 7, 9]
]


# 记录空数字的位置
def get_nonelocation(data):
    location = []
    for i in range(len(data)):
        for j in range(len(data[i])):
            if data[i][j] is None:
                location.append((i, j))
    return location


# 记录行可选值
def get_row_availed(data):
    availed = dict()
    for i in range(len(data)):
        availed[i] = select_digit - set(data[i])
    return availed


# 记录列可选值
def get_column_availed(data):
    availed = dict()
    for j in range(len(data[0])):
        exist_digit = set()
        for i in range(len(data)):
            if data[i][j]:
                exist_digit.add(data[i][j])
        availed[j] = select_digit - exist_digit
    return availed


# 获取每个区间的可选值（从左到右3x3一组，命名为区间(0,0)、(0,1)...(2,2)）
def get_span_availed(data):
    availed = dict()
    exist_digit = dict()
    for i in range(len(data)):
        for j in range(len(data[0])):
            availed[math.floor(i / 3), math.floor(j / 3)] = set()
            exist_digit[math.floor(i / 3), math.floor(j / 3)] = set()

    for i in range(len(data)):
        for j in range(len(data[0])):
            if data[i][j]:
                exist_digit[math.floor(i / 3), math.floor(j / 3)].add(data[i][j])

    for key in availed:
        availed[key] = select_digit - exist_digit[key]

    return availed


# 空位置可选值(思路：取行、列、区间的交集)
def none_point_availed(data):
    p_location = get_nonelocation(data)
    r_availed = get_row_availed(data)
    c_availed = get_column_availed(data)
    s_availed = get_span_availed(data)
    availed = dict()
    for i, j in p_location:
        availed[i, j] = set()

    for i, j in p_location:
        availed[i, j] = r_availed[i] & c_availed[j] & s_availed[math.floor(i / 3), math.floor(j / 3)]
        if not availed[i, j]:
            return -1
    return availed


# 将空值补上
def fill_none_point(data, p_availed, pre_data=None, index=0):
    if not p_availed:
        return data
    solution = True
    if p_availed == -1:
        data = pre_data  # 回退上一次的数据
        solution = False
        p_availed = none_point_availed(data)

    if solution:
        index = 0

    cros_nums = []
    for v in p_availed.values():
        cros_nums.append(len(v))

    min_cros_num = min(cros_nums)
    if min_cros_num == 1 and solution is False:
        raise RuntimeError("数独无解")

    pre_data = copy.deepcopy(data)  # 操作之前，先备份一份数据
    for k, v in p_availed.items():
        if min_cros_num == 1 and len(v) == 1:
            data[k[0]][k[1]] = list(v)[0]
        elif len(v) == min_cros_num:
            data[k[0]][k[1]] = list(v)[index]
            index += 1
            break

    p_availed = none_point_availed(data)
    fill_none_point(data, p_availed, pre_data, index)


if __name__ == "__main__":
    for row in s_data:
        print(row)
    none_availed = none_point_availed(s_data)
    fill_none_point(s_data, none_availed)
    for row in s_data:
        for var in row:
            if var is None:
                raise RuntimeError("数独无解")
    for row in s_data:
        print(row)
